package dmsxl.dandiaozhan;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Author: Zhang Dongwei
 * Date: 2023/9/27 12:18
 */
public class ddz4_42 {
    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap1(height));
    }

//    自己写的，时间复杂度很高
    public static int trap1(int[] height) {
        int[] lmax = new int[height.length];
        int[] rmax = new int[height.length];
        int res = 0;
        for (int i = 1; i < height.length - 1; i++){
            for (int j = 0; j < i; j++){
                if (lmax[i] < height[j]){
                    lmax[i] = height[j];
                }
            }
            for (int j = i + 1; j < height.length; j++){
                if (rmax[i] < height[j]){
                    rmax[i] = height[j];
                }
            }
        }
        for (int i = 1; i < height.length - 1; i++){
            if (lmax[i] > height[i] && rmax[i] > height[i]){
                res = res + Math.min(lmax[i], rmax[i]) - height[i];
            }
        }
        return res;
    }

//    题解，单调栈
    public static int trap(int[] height) {
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int mid = stack.peek();
                stack.pop();
                if (!stack.isEmpty()) {
                    int h = Math.min(height[stack.peek()], height[i]) - height[mid];
                    int w = i - stack.peek() - 1;
                    res += h * w;
                }
            }
            stack.push(i);
        }
        return res;
    }
}
